package com.damin;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

/**
 * 三路快排
 * 
 * @param <T>
 */
public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {

    @Override
    protected void sort(T[] nums, int low, int high) {
        if (high <= low) {
            return;
        }
        logger.info("新一轮排序：low：{},high：{}", low, high);
        int lt = low, i = low + 1, gt = high;
        T pivot = nums[low];
        while (i <= gt) {
            logger.info("比较第{}个元素和{}", i + 1, pivot);
            int cmp = nums[i].compareTo(pivot);
            if (cmp < 0) {
                swap(nums, lt++, i++);
            } else if (cmp > 0) {
                swap(nums, i, gt--);
            } else {
                logger.info("i++");
                i++;
            }
        }
        sort(nums, low, lt - 1);
        sort(nums, gt + 1, high);
    }

    public static void main(String[] args) {
        Integer[] nums = new Integer[] {3, 32, 4, 47, 48, 4234, 5, 1};
        new ThreeWayQuickSort<Integer>().sort(nums);
        System.out.println(nums);
    }
}
